package LeetCode;

/**
 * @Author: Dijah
 * @Date: 2023/3/15 10:29
 * @Desc: 求x的平方根
 *  使用二分搜索的方式
 *
 *
 *  如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
 * 如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；
 * 如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
 *
 */
public class code_69_sqrt {
    public static int mySqrt(int x){
        if(x == 0){
            return 0;
        }
        if( x == 1){
            return 1;
        }
        int left = 1;
        int right = x / 2;
        //在区间[left...right]范围查找目标的元素
        while (left < right){
            int mid = left + (right - left + 1) / 2;
            if(mid > x / mid){
                //下一轮的搜索区间
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int i = mySqrt(8);
        System.out.println(i);
    }
}
